package datastructure.book.dp._2_linear_pre_section.single.all;

import org.junit.jupiter.api.Test;

public class _12_Solution {

    @Test
    public void test(){
        int[] slices = {1,2,3,4,5,6};
        System.out.println(maxSizeSlices(slices));
    }
    public int maxSizeSlices(int[] slices) {
        int max1 = maxSizeSlices(slices,0,slices.length-2);
        int max2 = maxSizeSlices(slices,1,slices.length-1);
        return Math.max(max1,max2);
    }

    private int maxSizeSlices(int[] slices, int start, int end) {
        int n = slices.length/3;
        int[][] dp = new int[slices.length-1][n+1];
        dp[0][1] = slices[start];
        dp[1][1] = Math.max(slices[start],slices[start+1]);
        for (int i = 2; i < dp.length; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i-1][j],dp[i-2][j-1] + slices[i+start]);
            }
        }
        return dp[dp.length-1][n];
    }
}
